1. Field of the Invention
The present invention relates to control systems for graphics output devices, and more particularly, a technique for preparing and printing pen-stroke image information on a raster-type output device.
2. History of the Prior Art
Serial printing mechanisms capable of producing random graphic and character images on a page have existed for some time in the form of dot matrix, ink jet, thermal and other printers. These devices typically operate by scanning a printhead or other print mechanism across a page while printing individual dots on the paper (or other printing medium), advancing the paper, then repeating the process. This process can also be accomplished by different sequences of motions of the printhead and the paper in combinations to produce stripes of image on the medium. The printhead may contain any number of printing elements, allowing multiple rows of dots (print lines), and/or sometimes multiple colors, to be printed in any single pass of the printhead. Some printers make multiple passes of the printhead in a single section of the paper, printing a single color in each pass.
These printing mechanisms are all speed constrained by printheads with limited printing frequency capabilities, typically on the order of 500-10,000 dots per second per printing element. Frequency constraints are the result of mechanical speed limitations or heat buildup (as in thermal and thermal ink jet), drop formation rates (ink jet), or other factors. As a result of these frequency constraints, these printers have typically limited their applications to those requiring only limited dot placement resolution on the printing medium.
Greater resolution using classical technologies would have a significant effect on throughput. To double the resolution would theoretically require twice as may dots to be printed per pass (to double the horizontal resolution) and would also require twice as many passes of the printhead to be made (to double the vertical resolution). The effect then would be to reduce throughput by a factor of four. Any increase in resolution by a factor of X would produce an X-squared reduction in throughput. To achieve truly high quality output using these technologies would have an unacceptable effect on throughput.
Graphics processors and vector-to-raster converters have typically taken the form of graphics information being input to the system and an array of dots being output to replicate the graphics input language as accurately as possible, given the resolution of the device. This is done without regard for the mechanical configuration or limitations of the mechanical device. That is, dots are placed at each point on the raster array which is closest to the desired vectors' positions.
To do this, the graphics processor must typically parse graphics language input (such as HPGL--Hewlett Packard Graphics Language) into a series of vectors. Complex commands such as characters, circles, etc. may result in multiple vectors being generated. Then, a vector-to-raster converter typically takes a resulting vector with endpoints x1, y1 and x2, y2. It converts this into an equivalent of the following form:
x1, y1
slope
length (in either x or y)
color (if the device produces color output)
Beginning at x1, y1, then, it increments y (or x) by one, adds the slope to x (or y), then finds the point on the output array closest to this result. The converter then repeats this process until it reaches the end of the vector and repeats the entire process for each vector to be printed. Only after converting all vectors for a given section of output can that output begin, since the last vector may begin at the first position to be printed.
Some converters perform this operation on the entire plot file before beginning to print. Others convert on the fly, performing these operations on only a band of output at a time (banded vector to raster converters). These converters sometimes use sorting and sections of vectors to improve their efficiency. None of these techniques, however, is designed to change the eventual placement of dots on the output medium. They are merely different methods of trading memory requirements with processing time.
Printhead control has also been done with little regard to the capabilities of the printhead. Although most printing mechanisms typically skip over large blank areas of output, when they print they virtually always do so at a single, preset speed consistent with the maximum dot placement density achievable for a pre-selected resolution (e.g. letter quality or draft). Again, they have not looked at how they may take advantage of processing or limit their speed constraints by treating the entire printing process as a system rather than a set of black boxes (vector to raster converter, motor control, print element drivers, printhead and print elements).
In U.S. patent application Ser. No. 319,659, filed Mar. 3, 1989, "High Quality Plotting Technique for Raster Printing Devices" by inventor Rick A. Warp, published as PCT International Publication No. WO 90/09889 on Sept. 7, 1990, both of which are incorporated herein by reference, there is disclosed a technique which ameliorates many of the above problems.
The novelty of the technique derives in part from a recognition of the relationship between dot size on the writing medium and addressable resolution. In general, the dot diameter most appropriate is larger than the distance between addressable points.
A series of these dots, placed in close proximity to one another can form a line. In fact, these dots do not have to be placed at each addressable point to fully define that line, although they should be placed with full addressable resolution to maintain the image quality expected of that resolution. FIG. 7 shows two dots 300 and 302 near each other in a row of dots. The distance designated A represents the "scalloping" effect on the line created by the distance between dots. As the dots get closer together, A decreases; as they get farther apart, A increases. Because the human eye has limits in its ability to resolve A, dots can be spread apart until A is just below the level at which the eye can see the scalloping of the line.
As long as no information is lost when dots are spread as described here, the addressable resolution integrity is maintained while limiting the number of dots that must be placed on the printing medium. To determine whether information has been lost in this spreading process, the only difference between a theoretically perfect line of width equal to the dot diameter should be the scalloping. Potential losses of information, if improperly implemented, would most often occur at the ends of vectors. Loss of information could also occur along a vector if the full resolution of the device is sacrificed in the spreading process.
For the purposes of this technique, the various output dot print lines which the output device will print are considered divided into a number of major print lines interleaved with one or more minor print lines. In the preferred embodiment, there are three evenly spaced minor print lines interleaved between each pair of major print lines. Each major print line and its three subjacent minor print lines therefore make up a group of four print lines. The configuration is chosen such that for a large percentage of vectors, printing only those dots of the vector which occur on a selected one of the print lines in each group will result in a printed vector having no less than a desired level of line quality.
Each vector is then converted to a series of dots chosen to concentrate them as much as possible on the major print lines. However, if the slope that the vector makes with the print line is smaller than a predetermined value, for example 45.degree., then additional dots are required to achieve the desired level of line definition. For these vectors, extra dots are placed as much as possible on a first one of the minor print lines, the center interleaving print line in the preferred embodiment.
For vectors with slopes smaller than a second angle to the print lines, smaller than the first angle, printing only two dots per group of print lines may still not provide enough line definition. For these vectors a dot is placed on one or more of the remaining print lines in each group, again according to an order of preference. If the system includes additional minor print lines, and additional dots are still needed for the desired level of line definition on a particular vector, dots are placed on these print lines also in an established order of preference.
Accordingly, dots of a vector are designated for print only according to an established order of preference, and only as necessary to achieve the desired level of line definition. If only one dot per group of print lines is required for line definition, it is preferentially placed on a first, predetermined one of the print lines in each group (i.e. the major print line). If a second dot in each group is required for line definition, it is preferentially placed on a second predetermined print line of each group (preferably a print line half way between each of pair of major print lines). If a third dot in each group of print lines is needed, it is preferentially placed on a third predetermined one of the print lines in each group, and if a fourth dot in each group of print lines is needed, it is preferentially placed on a fourth predetermined print line in each group. This procedure can continue to whatever number of print lines are available in each group.
Once the vectors have been converted in this manner to dot patterns, or, if banded vector-to-raster conversion is being performed, then once all the vectors in a band are converted, the dot patterns may be printed according to the technique on any of the standard output devices using a novel adaptive speed control method. In particular, as a dot line is being printed, the print mechanism slows down or speeds up in accordance with the density of dots which must be printed in an upcoming portion of the print line. Thus, since the dot patterns for printing have been concentrated onto the print lines in a preferential order, the print mechanism will typically have its lowest average speed when printing the first print line of a group, a substantially higher average speed when printing the second predetermined print line of each group, a still higher average speed when printing the third predetermined print line of each group, and so on.
Print mechanisms often print on a plurality of print lines on each pass. For example, the Fujitsu DL3400 24-pin printer prints dots on 24 print lines on each pass of the printhead. In this case the distance between major print lines is defined equal to the vertical distance between pins on the printhead. Thus in the preferred embodiment, where each group of print lines consists of four print lines, 24 major print lines are printed on one pass. The paper is then advanced by one print line, and the first one of the minor print lines in each of the 24 groups are printed on the next pass. The paper is then advanced by one more print line and the second of the minor print lines is printed in each of the 24 groups. The paper is then advanced by yet another print line and the third of the minor print lines is also printed for each of the 24 groups. Finally, the paper is advanced by 93 print lines and printing of the next 24 groups of print lines begins.
In this situation the adaptive speed control must take into account the dot density of all 24 of the grid lines which are being printed on any particular pass. Accordingly, the printhead is adaptively sped up or slowed down in accordance with the highest density in the upcoming portion of all the print lines which are being printed on a particular pass, instead of in accordance with the dot density in an upcoming portion of only one of the print lines. Whether the print mechanism prints one print line per pass or more, the technique described in the Warp application results in a substantial speed improvement for a given level of image quality.
In another aspect of that technique, the endpoints of many of the input vectors are slightly modified to line them up with major print lines. This process creates an absolute error in position, but it is not perceptible to the eye and does increase speed substantially. However, vectors shorter than a predetermined number of dots may be omitted from the endpoint modification process.
In yet another aspect of the technique, the bit map generated by the vector-to-raster conversion technique described above may be post-processed in order to eliminate redundant dots on the output. Redundant dots are those which may be omitted without violating the desired level of quality. For example, where a string of three dots (either horizontally, vertically or on an angle) are spaced such that the outer two dots are within the maximum permissible spacing for the desired level of quality (see FIG. 7), the center dot then adds no information to the plot. Such redundancies can be created where multiple vectors are spaced closely or cross in close proximity to one another.
Redundancy elimination can be implemented to different degrees, depending on trade-offs between computational speed/power versus print speed. For example, a one-dimensional approach can be taken in which redundancies are detected and eliminated only within each respective dot line; diagonal and vertical redundancies are ignored.
In a two-dimensional approach, as in the vector-to-raster conversion, elimination of redundancies is done in such a way as to minimize the number of dots which must be printed on the interleaving passes of the printhead. This is done by eliminating first all the redundant dots which occur on the least preferred one of the print lines in each group, then eliminating all the redundant dots which occur in the next least preferred one of the print lines in each group, and so on up the order preference until redundant dots are eliminated from the major print lines. This order of elimination serves to concentrate dots in the same print lines as does the vector-to-raster converter.
The Warp application describes two means, among others, to obtain higher resolution in the horizontal (printhead travel) axis without increasing the printhead frequency or reducing the printhead travel velocity beyond those levels employed by lower resolution devices:
1) When performing vector-to-raster conversion on near-horizontal (class 7) or horizontal (class 1) vectors, dots to be placed on the same print line (printed by the same pin) may be spaced as far apart as possible while maintaining acceptable perceived line quality. The maximum acceptable spacing may be determined by the diameter of the dots produced by the printhead. When this spacing is maintained for all print lines in a pass band (the collection of print lines printed by a single pass of the printhead), the band can be printed with the printhead travelling at its nominal velocity. For example, if all dots are spaced at a maximum horizontal spacing of 4/720", the nominal printhead velocity may be 6 inches per second (IPS).
2) A number of redundancy removal algorithms may be employed to remove visually redundant dots that arise from the close proximity of multiple vectors. In general, many of these algorithms cause the removal of dots that are within certain distances of dots to both the left and right on the same print line. The algorithms may be designed to produce the desired dot spacing for maximum printing speed. One of the possible algorithms described in the Warp application, for example, is designed to prevent any two immediately adjacent dots on a print line from both printing.
Unfortunately, situations frequently arise in which these algorithms are not able to maintain the desired dot spacing for all print lines in a print band. For example, in a printer with 1/720" dot placement resolution and 4/720" maximum dot spacing, it is still possible for horizontal dot spacings of 2/720" and 3/720" to occur. In these situations the printhead velocity must be reduced, for example to 3 IPS, in order to print at least a portion of the pass band, or the frequency limit of the printhead would be exceeded.
These less-than-desirable dot spacings appear to arise from two different causes. First, there is a high probability that a class 1 or 7 vector (defined below) will have its endpoint at a coordinate that is less than 4/720" from a previously rasterized dot on the same print line. Secondly, the intersection of two vectors at certain angles can easily create situations in which two dots, one from each vector, are less than 4/720" apart horizontally. Neither of these problems are addressed adequately in the Warp application. The post-processing and redundancy removal algorithms, except for the one which prevents two immediately adjacent dots from both printing, are ineffective since the offending dots are not bounded by dots on both sides.
The techniques disclosed in the Warp application are best used with graphics output devices. Print speed limitations are also a problem in serial character printers such as common dot matrix printers, where a set of restrictions are imposed upon the placement of dots within the stored bitmaps for the supported fonts. These restrictions are sometimes known as phase rules. In situations where the number of potential dot positions on a given print line is larger than the number of dots that can be printed without unacceptably reducing the printhead velocity, the phase rules incorporate knowledge of the frequency limit of the printhead and the desired printing speed in order to dictate which potential dot positions may be used in the bitmap for any given character. For example, a rule might specify that if a dot for any print line is placed in a bitmap at a horizontal position n, no dots may be placed on the same print line at positions n+1 and n+2.
However, this phase rule technology appears to consist merely of "rules of thumb" that are applied by human font designers. Control systems for the printers designed to print these fonts do not appear to perform any dynamic modification of the font data for the purposes of increasing print speed. In one known instance, a printer employs three separate font tables, each created using different phase rules, for each of the three available print speed/resolution settings.
Accordingly, the present invention applies to raster printing devices in which the addressable resolution and the dot diameter are such that dots are larger than the distance between addressable points. This allows continuous horizontal line segments to be printed using only a subset of the potential dot positions with the dots equally spaced at a distance of (r*s) where r is the distance between addressable points and s is a "preferred" integral spacing factor.
An objective of the present invention is to overcome the deficiencies of the previously discussed prior art, to allow all raster bands to be printed at a printhead velocity v=(f*r*s) (where f is the maximum frequency of an individual pin in dots per second). Specifically, the invention eliminates all nonoptimal dot spacing situations that would require all or part of a raster band to be printed at a velocity of v'=(f*r*x) where x is an integer less than s.
For example, in one prior art printer, f=1080 Hz., r=1/720" and s=4, resulting in a nominal printhead velocity of v=6 IPS. Using the Warp technique, the potential nonoptimal dot spacings of 2/720" and 3/720" are both handled using the worst case values of x=2 and v'=3 IPS. The present invention, by completely eliminating these frequently occurring cases, has been demonstrated to result in overall printing speed performance improvements of up to 30 percent, depending on the particular data being printed.